Multicast is an operation to transmit information to multiple destinations, and is a requirement in high-performance networks. Many networking/computing applications exhibit the need for such multicast communication patterns. For example, audio/video multimedia conferencing, distance education, and video-on-demand services in a communication network, matrix multiplication and barrier synchronization in parallel/distributed computing systems, and record updates in a distributed database.
The network we consider is an N×N network that has N inputs and N outputs, and consists of one or more stages of switch modules. In a network, you generally have three types of communication—unicast, broadcast, and multicast. Unicast is the term used to describe communication where a piece of information is sent from one point to another point. In this case there is just one sender, and one receiver. Unicast transmission, in which a packet is sent from a single source to a specified destination, is the predominant form of transmission on LANs and within the Internet. All LANs (e.g. Ethernet) and IP networks support the unicast transfer mode, and most users are familiar with the standard unicast applications (e.g. http, smtp, ftp and telnet) which employ the TCP transport protocol.
Broadcast is the term used to describe communication where a piece of information is sent from one point to all other points. In this case there is just one sender, but the information is sent to all connected receivers. Broadcast transmission is supported on most LANs (e.g. Ethernet), and may be used to send the same message to all computers on the LAN (e.g. the address resolution protocol (arp) uses this to send an address resolution query to all computers on a LAN). Network layer protocols (such as IPv4) also support a form of broadcast that allows the same packet to be sent to every system in a logical network (in IPv4 this consists of the IP network ID and an all 1's host number).
Multicast is the term used to describe communication where a piece of information is sent from one or more points to a set of other points. In this case there is may be one or more senders, and the information is distributed to a set of receivers (there may be no receivers, or any other number of receivers). One example of an application which may use multicast is a video server sending out networked TV channels. Simultaneous delivery of high quality video to each of a large number of delivery platforms will exhaust the capability of even a high bandwidth network with a powerful video clip server. This poses a major scalability issue for applications which required sustained high bandwidth. One way to significantly ease scaling to larger groups of clients is to employ multicast networking.
Thus, multicasting is the networking technique of delivering the same packet simultaneously to a group of clients. IP multicast provides dynamic many-to-many connectivity between a set of senders (at least 1) and a group of receivers. The format of IP multicast packets is identical to that of unicast packets and is distinguished only by the use of a special class of destination address (class D IPv4 address) which denotes a specific multicast group. Since TCP supports only the unicast mode, multicast applications must use the UDP transport protocol.
Unlike broadcast transmission (which is used on some local area networks), multicast clients receive a stream of packets only if they have previously elect to do so (by joining the specific multicast group address). Membership of a group is dynamic and controlled by the receivers (in turn informed by the local client applications). The routers in a multicast network learn which sub-networks have active clients for each multicast group and attempt to minimize the transmission of packets across parts of the network for which there are no active clients.
The multicast mode is useful if a group of clients require a common set of data at the same time, or when the clients are able to receive and store (cache) common data until needed. Where there is a common need for the same data required by a group of clients, multicast transmission may provide significant bandwidth savings (up to 1/N of the bandwidth compared to N separate unicast clients).
The majority of installed LANs (e.g. Ethernet) are able to support the multicast transmission mode. Shared LANs (using hubs/repeaters) inherently support multicast, since all packets reach all network interface cards connected to the LAN. The earliest LAN network interface cards had no specific support for multicast and introduced a big performance penalty by forcing the adaptor to receive all packets (promiscuous mode) and perform software filtering to remove all unwanted packets. Most modern network interface cards implement a set of multicast filters, relieving the host of the burden of performing excessive software filtering.
For the purposes of this application, we define a valid multicast connection in such a switching network as a connection that the source of the multicast is an idle input of the network, and each destination of the multicast is an idle output of the network. Hereinafter, we simply refer to it as a multicast connection.
A multicast assignment is a collection of multicast connections with no overlapping allowed among the destinations of different sources. In a multicast assignment, the number of destinations from the same source is referred to as the fan-out of the source. A one-to-one mapping between the network inputs and outputs is a special case of a multicast assignment where the fan-out of each source is exactly one. Switching networks that can realize all possible multicast assignments are referred to as multicast switching networks. Moreover, a multicast switching network can be strictly nonblocking, wide-sense nonblocking, or rearrangeable. In a strictly nonblocking multicast network, any new multicast connection from a source to its destinations can be realized without any disturbance to existing connections in the network. In a wide-sense nonblocking multicast network, any new multicast connection from a source to its destinations can also be realized without any disturbance to existing connections in the network, given that the routing always follows a routing-control strategy. In a rearrangeable multicast network, rearrangements of on-going connections in the network may be needed to realize a new multicast connection.
Traditionally, the hardware cost of a switching network is measured by the number of its crosspoints. In general, an a×b switch has a×b crosspoints. The simplest design for a N×N nonblocking switching network is to adopt an N×N crossbar, which has N2 crosspoints. However, this hardware cost would be too high as N becomes large. Adopting a multistage network is a common approach to reducing the hardware cost of a switching network, since each stage of the network consists of smaller crossbars, and the total number of crosspoints of the network is much lower than that of an N×N crossbar.
The Clos-type network is a special type of multistage switching network with the following structural properties. For each switch module in a stage (except the last stage) of the network, its outputs are linked to all the switch modules in the next stage, with each output linked to a switch module and no two outputs linked to the same switch module. A typical three-stage Clos network has r switch modules of size n×m in the input stage, m switch modules of size r×r in the middle stage, and r switch modules of size m×n in the output stage with N=n×r and m>=n. The hardware cost of the network in terms of the number of crosspoints is {r×n×m+m×r2+r×m×n=m (2N+r2)}, which is proportional to m, the number of switch modules in the middle stage. Since the cost depends on all the terms that make up the total crosspoint count and depends on m, n, and r, minimizing the value of m may achieve low hardware cost for a three-stage Clos network. Alternatively, you can minimize n and or r as well assuming the other terms don't increase as a result.
Accordingly, there are long-felt industry needs for methods that improve upon conventional methods including the improved systems, methods and apparatus disclosed herein.
The features that are characteristic of the teachings, together with further objects and advantages, are better understood from the detailed description and the accompanying figures. Each of the figures is provided for the purpose of illustration and description only, and does not limit the present teachings.